package com.ting.test.algorithms.大厂刷题班;


import com.ting.test.algorithms.二叉树.TreeNode;

/**
 * 给一颗二叉树
 * 如果给一个节点安装相机，那么当前节点以及节点的父节点，和左右子节点都能够覆盖到
 * 求要全覆盖一颗树，最少需要多少相机
 * 利用二叉树的递归套路
 * 缺什么信息跟子树要
 */
public class 覆盖全树的最小相机数 {
    public static void main(String[] args) {
        TreeNode head = new TreeNode(3);
        int count = process(head);

    }

    private static int process(TreeNode head) {
        if (head == null) {
            return 0;
        }
        Info info = f(head);
        return Math.max(info.noCarmaCovered, Math.max(info.yesCarmaCovered, info.noCovered + 1));
    }

    private static Info f(TreeNode head) {
        if (head == null) {
            //空树可以被认为是没有摄像头但是被覆盖的情况
            return new Info(Integer.MAX_VALUE, Integer.MAX_VALUE, 0);
        }

        Info left = f(head.getLeft());//问左树要信息
        Info right = f(head.getRight());//问右树要信息

        //如果要想实现当前节点不安装摄像头，且当前节点不被覆盖到，但是当前节点以下的所有子节点都能够被覆盖到
        //对于这种情况，只能是当前节点的左右子节点不安装摄像头，但是能够被覆盖到
        int noCovered = left.noCarmaCovered + right.noCarmaCovered;

        //如果实现当前节点不安装摄像头，却要被覆盖到，那么实际上就是要左右子节点安装摄像头
        //这里需要注意，左右子树只要有一个安装摄像头，当前节点就能被覆盖到
        int noCarmaCovered = Math.min(left.noCarmaCovered + right.yesCarmaCovered,
                Math.min(left.yesCarmaCovered + right.yesCarmaCovered, left.yesCarmaCovered + right.noCarmaCovered));//表示当前head不装摄像)头


        //如果实现当前节点安装摄像头,其实左右节点是否安装摄像头已经无所谓了，直接取所有可能的组合的最小值
        int yesCarmaCovered = 1 + Math.min(left.noCovered, Math.min(left.yesCarmaCovered, left.noCarmaCovered)) + Math.min(right.noCovered, Math.min(right.noCarmaCovered, right.yesCarmaCovered));//表示当前head要装摄像头

        return new Info(noCovered, yesCarmaCovered, noCarmaCovered);
    }


    public static class Info {
        private int noCovered;//表示当前节点没有被覆盖到，但是当前节点的所有子节点都能够被覆盖到
        private int yesCarmaCovered;//表示当前节点安装摄像头，当前节点以及其的所有子节点都能够被覆盖到
        private int noCarmaCovered;//表示当前节点没有安装摄像头，但是当前节点以及其的所有子节点都能够被覆盖到

        public Info(int noCovered, int yesCarmaCovered, int noCarmaCovered) {
            this.noCovered = noCovered;
            this.yesCarmaCovered = yesCarmaCovered;
            this.noCarmaCovered = noCarmaCovered;
        }

        public int getNoNoCovered() {
            return noCovered;
        }

        public int getYesCarmaCovered() {
            return yesCarmaCovered;
        }

        public int getNoCarmaCovered() {
            return noCarmaCovered;
        }
    }
}
